package algorithms.leaning.class05;

import common.util.MyUtil;

/**
 * 荷兰国旗问题
 * <p>
 * 给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。
 * 返回num的位置
 * 比如[1,2,3,4,1,6,7,8,9,5,6] m=6
 * 处理完后[1,2,3,4,1,5,6,6,7,8,9] 返回值[6,7]
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 *
 * @author guichang
 * @date 2021/5/31
 */

@SuppressWarnings("all")
public class Code2_快速排序_荷兰国旗 {

    public static void main(String[] args) {
        int[] array = MyUtil.createRandomArray(10, -5, 5);
        int num = array[array.length - 1];
        MyUtil.print("num: " + num);
        int index = 0; // 遍历数组的下标
        int less = -1; // 小于区, 最右的位置
        int more = array.length; // 大于区, 最左的位置
        while (index < more) {
            if (array[index] < num) {
                MyUtil.swap(array, index++, ++less);
            } else if (array[index] > num) {
                MyUtil.swap(array, index, --more);
            } else {
                index++;
            }
        }
        MyUtil.printInt(array);
        // 调整后num的坐标
        int[] newNums = {less + 1, more - 1};
        MyUtil.printInt(newNums);
    }

}